package 二叉树.路径总和2;

import java.util.*;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/3/20 16:40
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,new TreeNode(4,new TreeNode(11),null),new TreeNode(8,new TreeNode(13),new TreeNode(4)));
        List<List<Integer>> lists = pathSum2(root, 17);
        System.out.println(lists.toString());
    }

    static List<List<Integer>> ret = new LinkedList<List<Integer>>();
    static Deque<Integer> path = new LinkedList<Integer>();

    //DFS的思想 TODO
    public static List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }
    //先序遍历
    public static void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        //取出尾部元素  在递归的回溯过程中，如果当前层次不满足我们的要求，可以删除一个节点值
        path.pollLast();
    }




    //BFS的思想 TODO 未完待续
    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null){
            return result;
        }
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size > 0){
                TreeNode node = queue.poll();
                targetSum = targetSum - root.val;
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
                size--;
                if (targetSum > 0){
                    list.add(node.val);
                }
                if (targetSum == 0 && node.left == null && node.right == null){
                    result.add(list);
                }
            }
        }
        return result;
    }
}
